from typing import *


class Solution:

    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        arr = [] * (n * 2)

        def f(l, r):
            if l == r and r == 0:
                ans.append("".join(arr))
                return
            if l != r:
                arr.append(')')
                f(l, r - 1)
                arr.pop()
            if l > 0:
                arr.append('(')
                f(l - 1, r)
                arr.pop()

        f(n, n)
        return ans


so = Solution()
print(so.generateParenthesis(3))
print(so.generateParenthesis(1))